/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function (n, dislikes) {
  let graph = []
  for (let i = 0; i <= n; i++) {
    graph[i] = []
  }
  for (let edge of dislikes) {
    let from = edge[0]
    let to = edge[1]
    graph[from].push(to)
    graph[to].push(from)
  } // 图构件好了
  let ok = true
  let color = new Array(n + 1).fill(false)
  let visited = new Array(n + 1).fill(false)
  for (let i = 0; i <= n; i++) {
    dfs(i)
  }
  function dfs (s) {
    if (!ok) return
    visited[s] = true
    for (let v of graph[s]) {
      if (!visited[v]) {
        color[v] = !color[s]
        dfs(v)
      } else {
        if (color[v] === color[s]) {
          ok = false
          return
        }
      }
    }
  }
  return ok
};
let n = 4, dislikes = [[1, 2], [1, 3], [2, 4]]
console.log(possibleBipartition(n, dislikes))